home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / window / _graph_edit.c next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  12.8 KB  |  607 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _graph_edit.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/graph_edit.h>
  17. #include <LEDA/graph_alg.h>
  18. #include <LEDA/node_matrix.h>
  19.  
  20.  
  21. static window*           Wp;
  22. static GRAPH<point,int>* Gp;
  23. static node_matrix<int>  M;
  24.  
  25.  
  26. static color node_color = green;
  27. static color edge_color = black;
  28. static bool  directed;
  29.  
  30. static int x_min, x_max, y_min, y_max;
  31. static double node_radius;
  32.  
  33. static list<point> cursor_in_edges;
  34. static list<point> cursor_out_edges;
  35.  
  36.  
  37. static void draw_node_cursor(double x, double y)
  38. {
  39.   point q(x,y);
  40.   point p;
  41.   forall(p,cursor_in_edges) Wp->draw_edge(p,q);
  42.   forall(p,cursor_out_edges) Wp->draw_edge(q,p);
  43.   Wp->draw_node(q); 
  44. }
  45.  
  46.  
  47.  
  48. static void draw_node(node v)
  49. { Wp->draw_text_node((*Gp)[v],string("%d",index(v)),node_color); }
  50.  
  51.  
  52.  
  53.  
  54. static void draw_edge(node v, node w)
  55. { 
  56.   // M(v,w) = number of edges from v to w (defines thickness of drawn edge)
  57.  
  58.   if (v == w) return; // still cannot draw self-loops 
  59.  
  60.   if (M(v,w) == 0) return;  // there is no edge (v,w)
  61.  
  62.   int lw_save = Wp->set_line_width(M(v,w));
  63.  
  64.   segment s(Gp->inf(v),Gp->inf(w));
  65.  
  66.   if (directed) 
  67.     if (M(w,v) == 0)
  68.        Wp->draw_edge_arrow(s,edge_color);
  69.     else
  70.        Wp->draw_arc_edge_arrow(s,0.7*s.length(),edge_color);
  71.   else 
  72.     if (M(w,v) == 0)
  73.        Wp->draw_edge(s,edge_color); 
  74.     else
  75.        Wp->draw_arc_edge(s,0.7*s.length(),edge_color);
  76.  
  77.   Wp->set_line_width(lw_save);
  78. }
  79.  
  80.  
  81. static void message(window& W, string s)
  82. { W.del_message();
  83.   W.message(s + "                              ");
  84.  }
  85.  
  86. static edge find_edge(node v, node w)
  87. { edge e = Gp->first_adj_edge(v);
  88.   while (e != nil && target(e) != w) e = Gp->adj_succ(e);
  89.   return e;
  90.  }
  91.  
  92.  
  93. static node V(point p)  // returns node at position p
  94. { node v;
  95.   forall_nodes(v,*Gp)
  96.     if (p.distance(Gp->inf(v)) < node_radius) return v;
  97.   return nil;
  98.  }
  99.  
  100. void init_matrix(const graph& g)
  101. { edge e;
  102.   int n = 100;
  103.   if (g.number_of_nodes() > n) n = 2*g.number_of_nodes();
  104.   M.init(g,n,0);
  105.   forall_edges(e,g) M(source(e),target(e))++;
  106.  }
  107.  
  108.  
  109. static void read_graph(window& W, GRAPH<point,int>& G,string s,bool clear=false)
  110. {
  111.   if (s=="") 
  112.   { message(W,"No file.");
  113.     return;
  114.    }
  115.  
  116.   message(W,string("Reading file %s.",~s));
  117.  
  118.   GRAPH<point,int> X;
  119.   node v;
  120.   node w;
  121.  
  122.   int x = X.read(s);
  123.  
  124.   if (x == 1) 
  125.   { message(W,string("Cannot open file %s.",~s));
  126.     return;
  127.    }
  128.  
  129.   if (x == 2)
  130.   { message(W,"File is not written by graph_edit (random embedding).");
  131.     int max = int(W.xmax())-3;
  132.     int min = 2;
  133.     forall_nodes(v,X)
  134.       X[v] = point(random(min,max), random(min,max));
  135.    }
  136.  
  137.   if (clear) 
  138.   { G.clear(); 
  139.     W.clear(); 
  140.    }
  141.  
  142.   node_array<node> corr(X);
  143.  
  144.   forall_nodes(v,X) 
  145.   { node u = G.new_node(X[v]);
  146.     corr[v] = u;
  147.     draw_node(u);
  148.    }
  149.  
  150.   edge e;
  151.   forall_edges(e,X) 
  152.   { v = corr[source(e)];
  153.     w = corr[target(e)];
  154.     G.new_edge(v,w);
  155.     M(v,w)++;
  156.    }
  157.  
  158.   if (clear) init_matrix(G);
  159.  
  160.   forall_nodes(v,G)
  161.      forall_nodes(w,G) 
  162.         draw_edge(v,w);
  163.  
  164. }
  165.  
  166.  
  167.  
  168. static void save_graph(window& W, GRAPH<point,int>& G,string s)
  169. { if (s=="") 
  170.   { message(W,"Cannot open file.");
  171.     return;
  172.    }
  173.   message(W,string("writing to file %s",~s));
  174.   G.write(s);
  175.  }
  176.  
  177.  
  178. static void generate_graph(GRAPH<point,int>& G)
  179. {
  180.   panel P("GRAPH GENERATORS");;
  181.  
  182.   int n = 10;
  183.   int m = 20;
  184.  
  185.   P.int_item("# nodes", n,0,500);
  186.   P.int_item("# edges", m,0,500);
  187.  
  188.   P.button("random");
  189.   P.button("complete");
  190.   P.button("bi_random");
  191.   P.button("bi_complete");
  192.   P.button("planar");
  193.   P.button("grid");
  194.   P.button("triang");
  195.   P.button("exit");
  196.  
  197.   list<node> A,B;
  198.   node v;
  199.  
  200.   G.clear();
  201.  
  202.   node_array<double> xcoord(G);
  203.   node_array<double> ycoord(G);
  204.  
  205.   double w = x_max - x_min;
  206.   double h = y_max - y_min;
  207.  
  208.   double R  = (x_max-x_min)/2.5;
  209.   double x0 = (x_max-x_min)/2;
  210.   double y0 = (y_max-y_min)/2;
  211.  
  212.   int i = P.open(*Wp);
  213.  
  214.   switch(i)
  215.   {
  216.     case 0: random_graph(G,n,m);
  217.             break;
  218.     case 1: complete_graph(G,n);
  219.             break;
  220.  
  221.     case 2: random_bigraph(G,n,n,m,A,B);
  222.             break;
  223.  
  224.     case 3: complete_bigraph(G,n,n,A,B);
  225.             break;
  226.  
  227.     case 4: { random_planar_graph(G,xcoord,ycoord,n);
  228.               node v;
  229.               forall_nodes(v,G)  
  230.                  G[v] = point(x_min + w*xcoord[v], y_min + h*ycoord[v]);
  231.               break;
  232.              }
  233.  
  234.     case 5: { grid_graph(G,xcoord,ycoord,n);
  235.               node v;
  236.               forall_nodes(v,G)  
  237.                  G[v] = point(x_min + w*xcoord[v], y_min + h*ycoord[v]);
  238.               break;
  239.              }
  240.  
  241.     case 6: { triangulated_planar_graph(G,xcoord,ycoord,n);
  242.               node v;
  243.               forall_nodes(v,G)  
  244.                  G[v] = point(x_min + w*xcoord[v], y_min + h*ycoord[v]);
  245.               break;
  246.              }
  247.    }
  248.  
  249.    if ( i==2 || i==3 )
  250.    { double dy = (y_max-y_min)/(n+1);
  251.      double y = y_min + dy;
  252.      forall(v,A) 
  253.      { G[v] = point(x_min + (x_max-x_min)/4,y);
  254.        y += dy;
  255.       }
  256.      y = y_min + dy;
  257.      forall(v,B) 
  258.      { G[v] = point(x_max - (x_max-x_min)/4,y);
  259.        y += dy;
  260.       }
  261.      }
  262.  
  263.    if (i==0 || i==1) // circular embedding 
  264.    { double R  = (x_max-x_min)/2.5;
  265.      double x0 = (x_max-x_min)/2;
  266.      double y0 = (y_max-y_min)/2;
  267.      point  M(x0,y0);
  268.      double alpha = 0;
  269.      double step  = 6.2832/n;
  270.      forall_nodes(v,G)  
  271.      { G[v] = M.translate(alpha,R);
  272.        alpha+=step;
  273.       }
  274.     }
  275.  
  276.   init_matrix(G);
  277. }
  278.  
  279.  
  280. static void redraw_func()
  281. { Wp->set_mode(src_mode);
  282.   node v;
  283.   forall_nodes(v,*Gp) 
  284.   { draw_node(v);
  285.     node w;
  286.     forall_nodes(w,*Gp) draw_edge(v,w);
  287.    }
  288.   Wp->set_mode(xor_mode);
  289.  }
  290.  
  291.  
  292.  
  293. static void window_init(window& W, GRAPH<point,int>& G)
  294. { 
  295.   W.init(x_min,x_max,y_min,0);
  296.  
  297.   if (W.mono()) node_color = white;
  298.  
  299.   W.set_redraw(redraw_func);
  300.   W.set_mode(src_mode);
  301.  
  302.   node_radius = W.get_node_width()/W.scale();
  303.  
  304.   node v;
  305.   forall_nodes(v,G) 
  306.   { draw_node(v);
  307.     node w;
  308.     forall_nodes(w,G) draw_edge(v,w);
  309.    }
  310.  
  311.   W.set_mode(xor_mode);
  312.  
  313. }
  314.  
  315.  
  316.  
  317. void graph_edit(window& W, GRAPH<point,int>& G, bool dir, bool redraw)
  318. {
  319.   double x,y;
  320.   point  p,q;
  321.   int    key;
  322.  
  323.   Wp = &W;
  324.   Gp = &G;
  325.  
  326.   init_matrix(G);
  327.  
  328.   x_min = (int)W.xmin();
  329.   x_max = (int)W.xmax();
  330.   y_min = (int)W.ymin();
  331.   y_max = (int)W.ymax();
  332.  
  333.   directed = dir;
  334.   node_radius = W.get_node_width()/W.scale();
  335.  
  336.  
  337.   string filename = "graph.ggg";
  338.  
  339.   panel main_panel("GRAPH EDIT MAIN PANEL");
  340.   main_panel.text_item("");
  341.   main_panel.text_item("graph_edit: A Graph Editor For LEDA Graphs.");
  342.   main_panel.text_item("");
  343.   main_panel.string_item("file:",filename);
  344.   main_panel.button("load");
  345.   main_panel.button("read");
  346.   main_panel.button("save");
  347.   main_panel.button("redraw");
  348.   main_panel.button("clear");
  349.   main_panel.button("gen");
  350.   main_panel.button("zoom");
  351.   main_panel.button("params");
  352.   main_panel.button("help");
  353.   main_panel.button("done");
  354.  
  355.  
  356.  
  357.   panel help_panel("GRAPH EDIT OPERATIONS");
  358.   help_panel.text_item("                                             ");
  359.   help_panel.text_item("          left button        middle button    ");
  360.   help_panel.text_item("                                             ");
  361.   help_panel.text_item("        insert/move node      insert edge     ");
  362.   help_panel.text_item("(shift)   delete node         delete edge     ");
  363.   help_panel.text_item("                                             ");
  364.   help_panel.button("continue");
  365.  
  366.  
  367.   panel init_panel("SETTINGS");
  368.   init_panel.int_item("x_min",x_min);
  369.   init_panel.int_item("x_max",x_max);
  370.   init_panel.int_item("y_min",y_min);
  371.   init_panel.color_item("node color",node_color);
  372.   init_panel.color_item("edge color",edge_color);
  373.   init_panel.button("continue");
  374.  
  375.  
  376.  
  377.   main_panel.display(W,0,0);
  378.  
  379.   drawing_mode save = W.set_mode(xor_mode);
  380.  
  381.  
  382.   if (redraw) window_init(W,G);
  383.  
  384.   bool done = false;
  385.  
  386.   LEDA_WINDOW* wp;
  387.  
  388.   while ( ! done )
  389.   {
  390.     read_mouse(wp,x,y);
  391.  
  392.     if (wp == &W || wp == &main_panel) put_back_event();
  393.  
  394.  
  395.     if (wp == &main_panel)
  396.     { int k = main_panel.read();
  397.  
  398.       switch (k) { 
  399.  
  400.       case 0 : // load 
  401.                read_graph(W,G,filename,true);
  402.                break;
  403.  
  404.       case 1 : // read
  405.                read_graph(W,G,filename,false);
  406.                break;
  407.   
  408.       case 2 : // save
  409.                save_graph(W,G,filename);
  410.                break;
  411.  
  412.       case 3:  // redraw
  413.                window_init(W,G);
  414.                break;
  415.  
  416.       case 4:  // clear
  417.                W.clear();
  418.                G.clear();
  419.                init_matrix(G);
  420.                break;
  421.  
  422.       case 5:  // generate
  423.                generate_graph(G);
  424.                window_init(W,G);
  425.                break;
  426.  
  427.  
  428.       case 6:  // zoom
  429.                W.acknowledge("Sorry, zoom not implemented.");
  430.                break;
  431.  
  432.  
  433.       case 7:  // settings
  434.                init_panel.open();
  435.                window_init(W,G);
  436.                break;
  437.  
  438.       case 8:  // help
  439.                help_panel.open();
  440.                break;
  441.   
  442.  
  443.       case 9: done = true;
  444.               break;
  445.      }
  446.  
  447.      continue;
  448.     }
  449.  
  450.  
  451.      key = W.read_mouse(x,y);
  452.  
  453.      W.del_message();
  454.  
  455.      p = point(x,y);
  456.  
  457.      switch(key) {
  458.  
  459.      case 1:  { 
  460.                 node v = V(p);
  461.  
  462.                 if (v == nil)        // new node
  463.                 { v  = G.new_node(p);
  464.                   draw_node(v);
  465.                  }
  466.                 else                    // move node
  467.                 { 
  468.                   draw_node(v);
  469.  
  470.                   cursor_in_edges.clear();
  471.                   cursor_out_edges.clear();
  472.                   edge e;
  473.                   forall_in_edges(e,v)  
  474.                   { draw_edge(source(e),v);
  475.                     cursor_in_edges.append(G[source(e)]); 
  476.                    }
  477.                   forall_out_edges(e,v)
  478.                   { draw_edge(v,target(e));
  479.                     cursor_out_edges.append(G[target(e)]); 
  480.                    }
  481.                   W.read_mouse_action(draw_node_cursor,x,y);
  482.  
  483.                   forall_in_edges(e,v)  draw_edge(source(e),v);
  484.                   forall_out_edges(e,v) draw_edge(v,target(e));
  485.  
  486.  
  487.  
  488.                   point q(x,y);           // new position
  489.  
  490.                   if (V(q) != nil)        // position not free
  491.                   { draw_node(v);
  492.                     break;
  493.                    }
  494.  
  495.                   node w;
  496.  
  497.                   forall_nodes(w,G)    // remove adjacent edges
  498.                   { draw_edge(v,w);
  499.                     draw_edge(w,v);
  500.                    }
  501.  
  502.                   G[v] = q;
  503.                   draw_node(v);
  504.  
  505.                   forall_nodes(w,G)    // reinsert adjacent edges
  506.                   { draw_edge(v,w);
  507.                     draw_edge(w,v);
  508.                    }
  509.  
  510.                  }
  511.                 break;
  512.                }
  513.  
  514.  
  515.      case 2:  { // new edge
  516.                 
  517.                 node v = V(p);   // start node
  518.  
  519.                 if (v != nil)            
  520.                 { p = G[v];
  521.  
  522.                   W.draw_filled_node(p);   // highlight start node
  523.  
  524.                   W.read_mouse_seg(p.xcoord(),p.ycoord(),x,y);
  525.  
  526.                   point q(x,y);
  527.                   node w = V(q);
  528.  
  529.                   if (w == nil)      // no hit: create a new node w at q
  530.                   { w  = G.new_node(q);
  531.                     draw_node(w);
  532.                    }
  533.  
  534.                   draw_edge(v,w);   // delete possible edge drawings
  535.                   draw_edge(w,v);
  536.  
  537.                   G.new_edge(v,w);  // insert new edge
  538.                   M(v,w)++;
  539.  
  540.                   draw_edge(w,v);   // reinsert edge drawings
  541.                   draw_edge(v,w);
  542.  
  543.                   W.draw_filled_node(p);  // un-highlight start node
  544.                  }
  545.  
  546.                 break;
  547.                }
  548.  
  549.  
  550.  
  551.      // Shift + mouse key
  552.  
  553.  
  554.      case -1: { // delete node
  555.  
  556.                 node v = V(p);
  557.  
  558.                 if (v != nil) 
  559.                 { node w; 
  560.                   forall_nodes(w,G)    // remove adjacent edges
  561.                   { draw_edge(v,w);
  562.                     draw_edge(w,v);
  563.                     M(v,w) = M(w,v) = 0;
  564.                    }
  565.  
  566.                   draw_node(v);
  567.  
  568.                   G.del_node(v);
  569.                  }
  570.  
  571.                 }
  572.  
  573.      case -2: { // delete edge
  574.  
  575.                 node v = V(p);
  576.  
  577.                 if (v != nil) 
  578.                 { p = G[v];
  579.                   W.read_mouse_seg(p.xcoord(),p.ycoord(),x,y);
  580.                   q = point(x,y);
  581.                   node w = V(q);
  582.                   if (w != nil) 
  583.                   { edge e = find_edge(v,w);
  584.                     if (e != nil)
  585.                     { draw_edge(v,w);
  586.                       draw_edge(w,v);
  587.                       G.del_edge(e);
  588.                       M(v,w)--;
  589.                       draw_edge(w,v);
  590.                       draw_edge(v,w);
  591.                      }
  592.                    }
  593.                  }
  594.                 break;
  595.                }
  596.  
  597.  
  598.     } // switch
  599.  
  600.   } // for(;;)
  601.  
  602.   W.reset_frame_label();
  603.   W.set_mode(save);
  604.   W.set_redraw(nil);
  605. }
  606.  
  607.